Dieser Audiobeitrag wird von der Universität Erlangen-Nürnberg präsentiert.

So, fangen wir einfach mal an. Also, guten Morgen zur zweiten Übung, äh, kurz, Informationstheorie.

Die ganzen Basics bezüglich Entropie und Mutual Information haben wir letztes Mal gemacht.

Dieses Mal wird es ein bisschen anwendungsnäher mit dem Thema Quellenkodierung.

Was genau ist Quellenkodierung eigentlich?

Wenn wir eine Informationsquelle haben, dann könnt ihr davon sicher ausgehen, dass die Information, die wir daraus ziehen, mit relativ viel Redundanz zusammengepackt ist.

Ein relativ einfaches Beispiel, das relativ schön untermalt ist, ist dieser Satz hier.

Offensichtlich würde jeder von euch erkennen, dass der eigentliche Satz, der hier steht, das Wetter ist schön heißen soll.

Ich habe halt nur mehr oder weniger wahllos meinen Buchstaben weggelassen.

Trotzdem kann es jeder von euch verstehen.

Das heißt, die Information, die der Satz trägt, ist der gleiche, wie wenn ich das Ganze korrekt geschrieben hätte.

Gleichzeitig habe ich natürlich eins, zwei, drei, vier, fünf Buchstaben weniger gebraucht.

Das heißt, ich habe im Grunde genommen Redundanz rausgezogen und ich habe eine kompaktere Darstellung für diesen Satz gefunden.

Das Ganze ist jetzt natürlich relativ dämlicher Algorithmus, indem ich einfach sage, ich lasse ab und zu mal ein Buchstaben weg.

Das Ganze kann man natürlich deutlich eleganter lösen und auch effizienter.

Und wie solche effizienteren Varianten aussehen, damit wollen wir uns heute in der Übung beschäftigen.

Grundsätzlich gibt es bei Quellenkodierungen drei verschiedene Verfahren, sogenannte Variable Length to Block-Kodierungen,

Block to Variable Length und Block to Block-Kodierungen.

Wobei immer das erste die Quellensequenz und das zweite die Codessequenz bezeichnet.

Das bedeutet, wir fangen einfach mal an mit Block to Variable Length-Kodierungen.

Das bedeutet, ich habe einen Block einer fixen Länge, beispielsweise immer fünf Quellensymbole, die ich zusammenfasse.

Die Kodierung hat aber dann unterschiedliche Länge.

Wie schaffe ich es jetzt hier, die Redundanz zu reduzieren?

Ganz einfach, sehr häufig auftretenden Quellenwörtern, also sehr wahrscheinlichen Quellenwörtern, wird eine sehr kurze Codesquenz zugewiesen.

Umgekehrt, sehr unwahrscheinlichen Quellenwörtern wird eine sehr lange oder etwas längere Codesquenz zugewiesen.

Dadurch, dass natürlich die Wahrscheinlicheren häufiger auftreten, wird häufiger das kürzere Wort, das kürzere Codewort ausgewählt.

Dadurch habe ich dann im Mittel eine Kompression, die ich erreiche.

Jetzt gibt es noch eine wichtige Eigenschaft, die wir bei diesen Block to Variable Length Codes beachten müssen.

Das ist die sogenannte Präfixfreiheit.

Ein einfacher, nicht präfixfreier Code wäre der hier.

Was ist ein Präfix? Präfix bedeutet, dass ein Codewort am Anfang eines anderen Codeworts auftritt.

In diesem Fall also die Null.

Wenn ich jetzt hier so etwas empfange, dann habe ich keine Ahnung, heißt es jetzt viermal A, heißt es zweimal B, heißt es ABA, heißt es BAA oder so.

Das kann ich einfach nicht erkennen.

Wenn ich jetzt aber Präfixfreiheit voraussetze, das bedeutet mein B müsste eine 1 vorne stehen haben, damit habe ich keinen Präfix mehr hier.

Ist es ganz klar, was ich hier empfangen habe, es kann nur noch viermal das A gewesen sein.

Damit ein Code präfixfrei ist, gibt es ein paar Bedingungen, die erfüllt sein müssen.

Es gibt zwei wichtige, die wir uns jetzt hier zum Warnmachen bei der Aufgabe viermal anschauen werden.

Das eine ist die sogenannte Kraftschirrungleichung. Die sieht folgendermaßen aus, relativ einfach.

Gehen wir uns mal ganz kurz durch, was die einzelnen Variablen bedeuten.

Mc ist immer die Kardinalität des Code-Alphabets.

Wenn wir einen binären Code haben, dann ist es 2, ternär, 3 und so weiter.

K ist einfach nur die Anzahl unserer Code-Wörter.

Und ni ist die Code-Wortlänge von Code-Wort i.

Sprich, wir summieren über alle Code-Wörter auf, Kardinalität hoch, minus die Code-Wortlänge.

Und das Ganze soll eben kleiner gleich 1 sein.

Das Ganze ist gleichbedeutend mit einer Bedingung in einem Baum.

Und zwar, was ich gleich zeigen werde, wenn diese Gleichung erfüllt ist, ist es gleichbedeutend, dass kein Zwischenkno ein Code-Wort ist.

Wir können es uns mal am ersten Beispiel einfach anschauen.

Die Aufgabe ist hier relativ simpel. Wir haben also verschiedene Code-Wortlängen gegeben.